// Copyright (c) 2021 Presto Labs Pte. Ltd.
// Author: chunhui

#include "coin2/strategy/util/moving_window_top_percentile.h"

#include <algorithm>
#include <deque>
#include <random>
#include <utility>
#include <vector>

#include <gtest/gtest.h>

namespace coin2::strategy::util {

class SlowMovingWindowTopPercentile {
 public:
  SlowMovingWindowTopPercentile(int64_t timewindow, double percentile)
      : timewindow_(timewindow), percentile_(percentile) {}

  void Add(int64_t ts, double value) {
    while (!q_.empty() && ts - q_.front() > timewindow_) {
      q_.pop();
      val_.pop_front();
    }
    q_.push(ts);
    val_.push_back(value);
  }

  bool Get(double* value) {
    if (val_.size() == 1) {
      *value = val_[0];
      return true;
    }
    std::vector<double> tmp(val_.begin(), val_.end());
    std::sort(tmp.begin(), tmp.end());
    int size = tmp.size() - 1;
    auto id = static_cast<size_t>(size * percentile_);
    double x1 = static_cast<double>(id) / size;
    double x2 = static_cast<double>(id + 1) / size;
    double y1 = tmp[id];
    double y2 = tmp[id + 1];
    *value = y1 + (percentile_ - x1) * (y2 - y1) / (x2 - x1);
    return true;
  }

 private:
  int64_t timewindow_;
  double percentile_;
  std::queue<int64_t> q_;
  std::deque<double> val_;
};

void GenerateTestCase(
    size_t test_size,
    int num_range,
    int64_t window_size,
    std::vector<double>* value,
    std::vector<int64_t>* timestamp) {
  int64_t prev_ts = 16'000'000'000LL;
  std::random_device device;
  std::mt19937 generator(device());
  std::uniform_real_distribution<> val_distribution(1, num_range);
  std::uniform_int_distribution<> ts_distribution(1, (window_size / 200));
  for (size_t i = 0; i < test_size; ++i) {
    int64_t ts = prev_ts + ts_distribution(generator) % (window_size / 200) + 1;
    timestamp->push_back(ts);
    prev_ts = ts;
    value->push_back(val_distribution(generator));
  }
}

TEST(MovingWindowTopPercentileTest, Basic) {
  size_t test_size = 100000;
  int64_t moving_window = 1001;
  double percentile = 0.9;
  int num_range = 10000;
  MovingWindowPercentile mp(moving_window, percentile);
  SlowMovingWindowTopPercentile slmp(moving_window, percentile);
  std::vector<double> values;
  std::vector<int64_t> timestamp;
  GenerateTestCase(test_size, num_range, moving_window, &values, &timestamp);
  for (int i = 0; i < test_size; ++i) {
    mp.Add(timestamp[i], values[i]);
    slmp.Add(timestamp[i], values[i]);
    double actual = 0;
    double expected = 1;
    mp.Get(&actual);
    slmp.Get(&expected);
    EXPECT_EQ(actual, expected);
  }
}

}  // namespace coin2::strategy::util
